package hero.mps.leet_code_21;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeTwoSortedList {

    public void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果list1为空，则直接返回list2
        if(list1 == null) return list2;
        // 如果list2为空，则直接返回list1
        if (list2 == null) return list1;
        // 如果list1的值小于list2的值
        if (list1.val < list2.val) {
            // 递归调用mergeTwoLists函数，将list1的下一个节点和list2进行合并，并将结果赋值给list1的next
            list1.next = mergeTwoLists(list1.next, list2);
            // 返回list1
            return list1;
        }else {
            // 递归调用mergeTwoLists函数，将list1和list2的下一个节点进行合并，并将结果赋值给list2的next
            list2.next = mergeTwoLists(list1, list2.next);
            // 返回list2
            return list2;
        }
    }

    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode sentinel = new ListNode(-1);
        ListNode prev = sentinel;
        // 合并两个链表，直到其中一个链表为空
        while (list1 != null && list2 != null) {
            // 如果list1的当前节点值小于list2的当前节点值
            if (list1.val < list2.val) {
                // 将list1的当前节点接到prev的后面
                prev.next = list1;
                // 移动list1的指针到下一个节点
                list1 = list1.next;
            // 如果list1的当前节点值不小于list2的当前节点值
            }else {
                // 将list2的当前节点接到prev的后面
                prev.next = list2;
                // 移动list2的指针到下一个节点
                list2 = list2.next;
            }
            // 移动prev的指针到下一个节点
            prev = prev.next;
        }
        // 如果list1还有剩余节点，则将剩余节点接到prev的后面
        // 否则将list2的剩余节点接到prev的后面
        prev.next = list1 == null ? list2 : list1;
        // 返回合并后的链表的头节点
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new MergeTwoSortedList().mergeTwoLists1(new ListNode(1, new ListNode(2)), new ListNode(2, new ListNode(4)));
        new MergeTwoSortedList().printListNode(listNode);
    }
}
